BOJ_2169_로봇 조종하기

DP(Dynamic Programming)를 이용하여 푸는 문제
4개의 풀이 부분으로 나눌 수 있다

  1. 배열의 맨 첫 줄을 초기화한다
    왜냐면 맨 첫 줄에서 가능한 방향은 -> 밖에 없기 때문이다
    따라서 0부터 M-1까지 가며 누적 더하기를 해주면 된다

  2. temp 배열을 사용한다
    temp 배열이 필요한 이유는 오른쪽 방향과 아래 방향 비교 / 왼쪽 방향과 아래 방향 비교를 해서 저장해 둘 변수가 필요하기 때문이다
    단순하게 앞에서부터 오른쪽, 왼쪽, 아래를 비교한다면 오른쪽 배열의 값이 전혀 탐색되지 않았기 때문에 최대를 계산한 값 vs 그냥 처음 값 비교가 되어버린다
    즉, 어떤 루트로 가던 오른쪽 또는 왼쪽 중 하나는 계산하지 않은 값이다!

    그러면 양 쪽 다 계산된 값을 비교하려면 어떻게 해야할까?
    각각의 방향으로 탐색한 후에 둘을 비교하면 되는 것이다
    그래서 temp를 가로 길이가 M인 것으로 2칸 짜리를 선언하여 사용한다

  3. 오른쪽&아래 / 왼쪽&아래를 비교한 뒤 둘 중 큰 값을 dp에 넣어준다
    만약 앞서서 아래 방향을 탐색했다고 왼쪽 탐색할 때 아래를 비교해주지 않으면 3개를 동등하게 비교하는 것이 아니라 오른쪽-아래 vs 왼쪽 이 되기 때문에 두 번 다 넣어주어야 한다

  4. 각 비교를 시작하는 시작 지점에서는 아래 방향에서 밖에 올 수 없으므로 temp 배열을 따로 초기화해 준다

이 과정을 거치면 문제를 풀 수 있다

package BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
import java.util.stream.Stream;  
  
public class BJO_2169_로봇조종하기 {  
  
public static void main(String[] args) throws IOException {  
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
StringTokenizer st = new StringTokenizer(br.readLine());  
  
int N = Integer.parseInt(st.nextToken());  
int M = Integer.parseInt(st.nextToken());  
  
int[][] land = new int[N][M];  
for (int i = 0; i < N; i++) {  
land[i] = Stream.of(br.readLine().split(" ")).mapToIntparseInt).toArray(;  
}  
  
int[][] dp = new int[N][M];  
int[][] temp = new int[2][M];  
dp[0][0] = land[0][0];  
  
for (int i = 1; i < M; i++) {  
dp[0][i] = dp[0][i-1] + land[0][i];  
}  
  
for (int i = 1; i < N; i++) {  
// temp 배열 초기화  
temp[0][0] = dp[i-1][0] + land[i][0];  
for (int j = 1; j < M; j++) {  
temp[0][j] = Math.max(temp[0][j - 1], dp[i - 1][j]) + land[i][j];  
}  
  
temp[1][M-1] = dp[i - 1][M-1] + land[i][M-1];  
for (int j = M-2; j >= 0; j--) {  
temp[1][j] = Math.max(temp[1][j + 1], dp[i - 1][j]) + land[i][j];  
}  
  
for (int j = 0; j < M; j++) {  
dp[i][j] = Math.max(temp[0][j], temp[1][j]);  
}  
}  
  
System.out.println(dp[N-1][M-1]);  
}  
}

#dp